home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Folder / Problem 06 / Secret.cp < prev    next >
Encoding:
Text File  |  1998-06-18  |  28.4 KB  |  889 lines  |  [TEXT/CWIE]
  1. #include "Solution.h"
  2.  
  3. #include "ProblemUtils.h"
  4. #include "myqsort.h"
  5.  
  6. #include <stdio.h>
  7. #include <Files.h>
  8. #include <Errors.h>
  9.  
  10. #define PRINT_MOVES 0
  11. #define PRINT_PIECES 0
  12. #define PRINT_BOARD 0
  13. #define PRINT_CORRECT_RESULTS 1
  14.  
  15. #define kMaxPiecesRemaining 32
  16. #define kMaxMoves 1024
  17.  
  18. static char gCol[] = "abcdefgh";
  19. static char gRow[] = "12345678";
  20. static char gColor[] = " WB";
  21. static char gRank[] = "-pNBRQK";
  22. #define kKingCol 4
  23. #define kQueenCol 3
  24.  
  25.  
  26. static OSErr SortPiecesCmp(void *p1, void *p2, short *result)
  27. {
  28.     ChessPiece *piece1=(ChessPiece *)p1;
  29.     ChessPiece *piece2=(ChessPiece *)p2;
  30.     if (piece1->pieceLocation.row < piece2->pieceLocation.row)
  31.         {*result = -1; return noErr;}
  32.     else if (piece1->pieceLocation.row > piece2->pieceLocation.row)
  33.         {*result = 1; return noErr;}
  34.     if (piece1->pieceLocation.col < piece2->pieceLocation.col)
  35.         {*result = -1; return noErr;}
  36.     else if (piece1->pieceLocation.col > piece2->pieceLocation.col)
  37.         {*result = 1; return noErr;}
  38.     *result = 0; return noErr;
  39. }
  40.  
  41. static OSErr SortMovesCmp(void *m1, void *m2, short *result)
  42. {
  43.     ChessMove *move1=(ChessMove *)m1;
  44.     ChessMove *move2=(ChessMove *)m2;
  45.     if (move1->fromSquare.row < move2->fromSquare.row)
  46.         {*result = -1; return noErr;}
  47.     else if (move1->fromSquare.row > move2->fromSquare.row)
  48.         {*result = 1; return noErr;}
  49.     if (move1->fromSquare.col < move2->fromSquare.col)
  50.         {*result = -1; return noErr;}
  51.     else if (move1->fromSquare.col > move2->fromSquare.col)
  52.         {*result = 1; return noErr;}
  53.     if (move1->toSquare.row < move2->toSquare.row)
  54.         {*result = -1; return noErr;}
  55.     else if (move1->toSquare.row > move2->toSquare.row)
  56.         {*result = 1; return noErr;}
  57.     if (move1->toSquare.col < move2->toSquare.col)
  58.         {*result = -1; return noErr;}
  59.     else if (move1->toSquare.col > move2->toSquare.col)
  60.         {*result = 1; return noErr;}
  61.     if (move1->capture && !move2->capture)
  62.         {*result = -1; return noErr;}
  63.     else if (!move1->capture && move2->capture)
  64.         {*result = 1; return noErr;}
  65.     if (move1->capture && move2->capture) {
  66.         if (move1->capturedSquare.row < move2->capturedSquare.row)
  67.             {*result = -1; return noErr;}
  68.         else if (move1->capturedSquare.row > move2->capturedSquare.row)
  69.             {*result = 1; return noErr;}
  70.     }
  71.     *result = 0; return noErr;
  72. }
  73.  
  74. static OSErr ReadUInt32FromHandle( Handle data, UInt32 *number )
  75. {
  76.     OSErr err;
  77.     char line[MAX_LINE_LEN];
  78.     char *p;
  79.  
  80.     p = line;    
  81.     if ( ProblemReadLineFromHandle( data, line, MAX_LINE_LEN ) && ProblemGetUInt32( &p, number ) && *p == 0 ) {
  82.         err = noErr;
  83.     } else {
  84.         err = -1;
  85.     }
  86.     return err;
  87. }
  88.  
  89. static OSErr ReadChessMoveFromHandle( Handle data, char *side, 
  90.     char *fromCol, char *fromRow,char *move, 
  91.     char *toCol, char *toRow, char *captureCol, char *captureRow)
  92. {
  93.     OSErr err;
  94.     char line[MAX_LINE_LEN];
  95.     char *p;
  96.  
  97.     p = line;    
  98.     if ( ProblemReadLineFromHandle( data, line, MAX_LINE_LEN ) && *p == 0 ) {
  99.         err = noErr;
  100.     } else {
  101.         err = -1;
  102.     }
  103.     *side = line[0];
  104.     *fromCol = line[2];
  105.     *fromRow = line[3];
  106.     *move = line[4];
  107.     *toCol = line[5];
  108.     *toRow = line[6];
  109.     if (*move=='x') {
  110.         *captureCol = line[8];
  111.         *captureRow = line[9];
  112.     } else {
  113.         *captureCol = 0;
  114.         *captureRow = 0;
  115.     }
  116.     return err;
  117. }
  118.  
  119. static OSErr ReadMoves(Handle indata, UInt32 numMoves, ChessMove *moves)
  120. {
  121.     OSErr err = noErr;
  122.     for (int j=0; j<numMoves;j++) {
  123.         char p,c1,r1,c2,r2,c3,r3,move;
  124.         err = ReadChessMoveFromHandle (indata, &p, &c1, &r1, &move, &c2, &r2, &c3, &r3);
  125.         if ((j&1)==0) {
  126.             if (p!='W') DebugStr("\p expecting white move");
  127.         } else {
  128.             if (p!='B') DebugStr("\p expecting black move");
  129.         }
  130.         if (move=='x') {
  131.             moves[j].capture = true;
  132.             moves[j].capturedSquare.col = c3-gCol[0];
  133.             moves[j].capturedSquare.row = r3-gRow[0];
  134.         } else {
  135.             moves[j].capture = false;
  136.             moves[j].capturedSquare.col = 0;
  137.             moves[j].capturedSquare.row = 0;
  138.         }
  139.         moves[j].fromSquare.col = c1-gCol[0];
  140.         moves[j].fromSquare.row = r1-gRow[0];
  141.         moves[j].toSquare.col = c2-gCol[0];
  142.         moves[j].toSquare.row = r2-gRow[0];
  143.     }
  144.     return err;
  145. }
  146.  
  147. typedef struct Piece {
  148.     PieceColor color;
  149.     PieceRank rank;
  150. } Piece;
  151.  
  152. typedef struct Board {
  153.     Piece sq[8][8];
  154.     Square kingSq;
  155.     ChessMove lastMove;
  156.     Boolean pieceNeverMoved[8][8];
  157. } Board;
  158.  
  159. static void InitBoard(Board *b)
  160. {
  161.     int row,col;
  162.     for (col=0; col<8; col++) {
  163.         b->sq[0][col].color = b->sq[1][col].color = kWhite;
  164.         b->sq[7][col].color = b->sq[6][col].color = kBlack;
  165.         b->sq[2][col].color = b->sq[3][col].color = kEmpty;
  166.         b->sq[4][col].color = b->sq[5][col].color = kEmpty;
  167.         b->sq[1][col].rank = b->sq[6][col].rank = kPawn;
  168.         b->sq[2][col].rank = b->sq[3][col].rank = kNone;
  169.         b->sq[4][col].rank = b->sq[5][col].rank = kNone;
  170.     }
  171.     b->sq[0][0] .rank= b->sq[0][7].rank = b->sq[7][0].rank = b->sq[7][7].rank = kRook;
  172.     b->sq[0][1].rank = b->sq[0][6].rank = b->sq[7][1].rank = b->sq[7][6].rank = kKnight;
  173.     b->sq[0][2].rank = b->sq[0][5].rank = b->sq[7][2].rank = b->sq[7][5].rank = kBishop;
  174.     b->sq[0][kQueenCol].rank = b->sq[7][kQueenCol].rank = kQueen;
  175.     b->sq[0][kKingCol].rank = b->sq[7][kKingCol].rank = kKing;
  176.     for (row=0; row<8; row++) {
  177.         for (col=0; col<8; col++) {
  178.             b->pieceNeverMoved[row][col] = true;
  179.         }
  180.     }
  181.     b->lastMove.fromSquare.row = b->lastMove.fromSquare.col = 0xffff;
  182.     b->lastMove.toSquare.row = b->lastMove.toSquare.col = 0xffff;
  183. }
  184.  
  185. #if PRINT_PIECES
  186. static void PrintPieces(UInt32 numPieces, ChessPiece *piece, char *s)
  187. {
  188.     int j;
  189.     printf("%s %ld\n", s,numPieces);
  190.     for (j=0; j<numPieces; j++) {
  191.         printf("%c%c %c%c\n",
  192.             gColor[piece[j].whichColor],gRank[piece[j].whichRank],
  193.             gCol[piece[j].pieceLocation.col],gRow[piece[j].pieceLocation.row]);
  194.     }
  195. }
  196. #else
  197. static void PrintPieces(UInt32 numPieces, ChessPiece *piece, char *s) {
  198. #pragma unused(numPieces)
  199. #pragma unused(piece)
  200. #pragma unused(s)
  201. };
  202. #endif
  203.  
  204. #if PRINT_MOVES
  205. static void PrintMoves(UInt32 numMoves, ChessMove *move, char *s)
  206. {
  207.     int j;
  208.     printf("%s %ld\n",s,numMoves);
  209.     for (j=0; j<numMoves; j++) {
  210.         printf("%d %c%c%c%c%c",j,
  211.             gCol[move[j].fromSquare.col],gRow[move[j].fromSquare.row],
  212.             move[j].capture ? 'x' : '-',
  213.             gCol[move[j].toSquare.col],gRow[move[j].toSquare.row]);
  214.         if (move[j].capture) {
  215.             printf(" %c%c\n",
  216.                 gCol[move[j].capturedSquare.col],gRow[move[j].capturedSquare.row]);
  217.         } else {
  218.             printf("\n");
  219.         }
  220.     }
  221. }
  222. #else
  223. static void PrintMoves(UInt32 numMoves, ChessMove *move, char *s) {
  224. #pragma unused(numMoves)
  225. #pragma unused(move)
  226. #pragma unused(s)
  227. };
  228. #endif
  229.  
  230. #if PRINT_BOARD
  231. static void PrintBoard(Board *b)
  232. {
  233.     int row,col;
  234.     printf("    a  b  c  d  e  f  g  h \n");
  235.     for (row=7; row>=0; row--) {
  236.         printf("%2d ",row+1);
  237.         for (col=0; col<8; col++) {
  238.             printf("%c%c ",gColor[b->sq[row][col].color], gRank[b->sq[row][col].rank]);            
  239.         }
  240.         printf("\n");
  241.     }
  242.     printf("    %c%c%c%c%c\n\n",
  243.         gCol[b->lastMove.fromSquare.col],gRow[b->lastMove.fromSquare.row],
  244.         b->lastMove.capture ? 'x' : '-',
  245.         gCol[b->lastMove.toSquare.col],gRow[b->lastMove.toSquare.row]    );
  246. }
  247. #else
  248. static void PrintBoard(Board *b) {
  249. #pragma unused(b)
  250. };
  251. #endif
  252.  
  253. static PieceColor OtherColor(PieceColor c)
  254. {
  255.     return (PieceColor)(3 - (int)c);    /* white is 1, black is 2 */
  256. }
  257.  
  258. static Boolean FindKing(Board *b,PieceColor color, Square *kingSq)
  259. {
  260.     int row,col;
  261.     for (row=0; row<8; row++)
  262.         for (col=0; col<8; col++) {
  263.             if ( (b->sq[row][col].color == color) && (b->sq[row][col].rank==kKing)) {
  264.                 kingSq->row = row;    kingSq->col = col;    return true;
  265.             }
  266.         }
  267.     return false;
  268. }
  269.  
  270. static void MovePiece(Board *b, ChessMove *m, PieceColor colorToMove)
  271. {
  272.     int fromRow = m->fromSquare.row;
  273.     int fromCol = m->fromSquare.col;
  274.     int toRow = m->toSquare.row;
  275.     int toCol = m->toSquare.col;
  276.     PieceColor ourColor = b->sq[fromRow][fromCol].color;
  277.     int homeRow = (ourColor==kWhite) ? 0 : 7;
  278.     if (colorToMove != ourColor) printf("** ERR moving wrong color piece\n");
  279.     if (!m->capture) {
  280.         if (b->sq[toRow][toCol].color != kEmpty) {
  281.             printf(" ** bad move fromSq=(%d %d) toSq=(%d %d) our color=%d other color=%d\n",
  282.                 fromRow,fromCol,toRow,toCol,
  283.                 b->sq[fromRow][fromCol].color,b->sq[toRow][toCol].color);
  284.         }
  285.     } else {  // debug test fails incorrectly for en passant
  286. //        if (b->sq[toRow][toCol].color != OtherColor(b->sq[fromRow][fromCol].color)) {
  287. //            printf(" ** bad capture fromSq=(%d %d) toSq=(%d %d) our color=%d other color=%d\n",
  288. //                fromRow,fromCol,toRow,toCol,
  289. //                b->sq[fromRow][fromCol].color,b->sq[toRow][toCol].color);
  290. //        }
  291.         /* includes en passant */
  292.         b->sq[m->capturedSquare.row][m->capturedSquare.col].color = kEmpty;
  293.         b->sq[m->capturedSquare.row][m->capturedSquare.col].rank = kNone;
  294.     }
  295.     /* check castle */
  296.     if ( (b->sq[fromRow][fromCol].rank == kKing) && (fromRow==homeRow) && (fromCol==kKingCol) && 
  297.           (b->sq[fromRow][fromCol].color==ourColor) ) {
  298.             if ( (toCol==2) && (b->sq[fromRow][1].rank==kRook)) {
  299.                 b->sq[fromRow][3].color = b->sq[fromRow][0].color;
  300.                 b->sq[fromRow][3].rank = b->sq[fromRow][0].rank;
  301.                 b->sq[fromRow][0].color = kEmpty;
  302.                 b->sq[fromRow][0].rank = kNone;
  303.             } else if ( (toCol==6)  && (b->sq[fromRow][7].rank==kRook) ) {
  304.                 b->sq[fromRow][5].color = b->sq[fromRow][7].color;
  305.                 b->sq[fromRow][5].rank = b->sq[fromRow][7].rank;
  306.                 b->sq[fromRow][7].color = kEmpty;
  307.                 b->sq[fromRow][7].rank = kNone;
  308.             }
  309.     }
  310.     /* check pawn promotion */
  311.     if ( (b->sq[fromRow][fromCol].rank == kPawn) && (b->sq[fromRow][fromCol].color==ourColor) &&
  312.           (toRow==7-homeRow) ) {
  313.           /* promote in place, move code will update proper location */
  314.         b->sq[toRow][toCol].rank = kQueen;
  315.     } 
  316.     /* update board */
  317.     b->sq[toRow][toCol].color = b->sq[fromRow][fromCol].color;
  318.     b->sq[toRow][toCol].rank = b->sq[fromRow][fromCol].rank;
  319.     b->sq[fromRow][fromCol].color = kEmpty;
  320.     b->sq[fromRow][fromCol].rank = kNone;
  321.     b->pieceNeverMoved[fromRow][fromCol] = false;
  322.     b->pieceNeverMoved[toRow][toCol] = false;
  323.     b->lastMove = *m;
  324.     FindKing(b,ourColor,&b->kingSq);
  325. }
  326.  
  327. static SInt16 gDeltaRow[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
  328. static SInt16 gDeltaCol[8] =  {-1, -1, 0, 1, 1, 1, 0, -1};
  329. static SInt16 gKnightDeltaRow[8] = {1,2,2,1,-1,-2,-2,-1};
  330. static SInt16 gKnightDeltaCol[8] = {-2,-1,1,2,2,1,-1,-2};
  331.  
  332. static Boolean LegalSquare(SInt16 row, SInt16 col) {    /* note need for signed value */
  333.     return ((row>=0) && (row<8) && (col>=0) && (col<8));
  334. }
  335.  
  336. static Boolean LegalRelSquare(Board *b, SInt16 row, SInt16 col, int dir, int dist, Piece *sq)
  337. {
  338.     Boolean result;
  339.     row += gDeltaRow[dir]*dist;
  340.     col += gDeltaCol[dir]*dist;
  341.     result = LegalSquare(row, col);
  342.     if (result) *sq = b->sq[row][col];
  343.     return result;
  344. }
  345.  
  346. static Boolean LegalKnightRelSquare(Board *b, SInt16 row, SInt16 col, int dir, Piece *sq)
  347. {
  348.     Boolean result;
  349.     row += gKnightDeltaRow[dir];
  350.     col += gKnightDeltaCol[dir];
  351.     result = LegalSquare(row,col);
  352.     if (result) *sq = b->sq[row][col];
  353.     return result;
  354. }
  355.  
  356. static Boolean MovesDiagonally(PieceRank rank, UInt16 dist) {
  357.     return ((rank==kQueen)||(rank==kBishop)||( (dist==1) && (rank==kKing) ) );
  358. }
  359.  
  360. static Boolean MovesRectangularly(PieceRank rank, UInt16 dist) {
  361.     return ((rank==kQueen)||(rank==kRook)||( (dist==1) && (rank==kKing) ) );
  362. }
  363.  
  364. static Boolean SquareIsAttacked(Board *b, SInt16 row, SInt16 col)
  365. {
  366.     Piece onSquare;
  367.     PieceColor ourColor = b->sq[row][col].color;
  368.     PieceColor opponentColor = OtherColor(ourColor);
  369.     int dir,dist;
  370.     
  371.     for (dir=1; dir<8; dir+=2) {    /* check diagonals */
  372.         for (dist=1; dist<8; dist++) {    /* check distance */
  373.             if (!LegalRelSquare(b, row, col, dir, dist, &onSquare)) break;
  374.             if (onSquare.color == kEmpty) break;
  375.             if (onSquare.color == ourColor) break;
  376.             if (onSquare.color == opponentColor) {
  377.                 if ( MovesDiagonally(onSquare.rank,dist) )
  378.                     return true;
  379.             } else break;
  380.         }
  381.     }
  382.     
  383.     for (dir=0; dir<8; dir+=2) {    /* check files */
  384.         for (dist=1; dist<8; dist++) {    /* check distance */
  385.             if (!LegalRelSquare(b, row, col, dir, dist, &onSquare)) break;
  386.             if (onSquare.color == kEmpty) break;
  387.             if (onSquare.color == ourColor) break;
  388.             if (onSquare.color == opponentColor) {
  389.                 if ( MovesRectangularly(onSquare.rank,dist) )
  390.                     return true;
  391.             } else {
  392.                 break;
  393.             }
  394.         }
  395.     }
  396.     
  397.     for (dir=0; dir<8; dir++) {    /* check knights */
  398.         if (!LegalKnightRelSquare(b, row, col, dir, &onSquare)) continue;
  399.         if (onSquare.color == kEmpty) continue;
  400.         if (onSquare.color == ourColor) continue;
  401.         if (    (onSquare.color == opponentColor) && (onSquare.rank == kKnight) ) 
  402.             return true;
  403.     }
  404.  
  405.     /* check pawns */
  406.     if (LegalRelSquare(b, row, col, (ourColor==kWhite) ? 1 : 8-1, 1, &onSquare))
  407.         if ( (onSquare.color==opponentColor) && (onSquare.rank==kPawn)) 
  408.             return true;
  409.     if (LegalRelSquare(b, row, col, (ourColor==kWhite) ? 3 : 8-3, 1, &onSquare))
  410.         if ( (onSquare.color==opponentColor) && (onSquare.rank==kPawn)) 
  411.             return true;
  412.     return false;
  413. }
  414.  
  415. static void CreateMove(ChessMove *m, UInt16 row, UInt16 col, int dir, int dist, Piece *sq)
  416. {
  417.     m->fromSquare.row = row;
  418.     m->fromSquare.col = col;
  419.     m->toSquare.row = row + gDeltaRow[dir]*dist;
  420.     m->toSquare.col = col + gDeltaCol[dir]*dist;
  421.     m->capture = false;
  422.     if (sq->color != kEmpty) {    /* pawns need to be handled separately */
  423.         m->capture = true;
  424.         m->capturedSquare = m->toSquare;
  425.     }
  426. }
  427.  
  428. static void CreateKnightMove(ChessMove *m, UInt16 row, UInt16 col, int dir, Piece *sq)
  429. {
  430.     m->fromSquare.row = row;
  431.     m->fromSquare.col = col;
  432.     m->toSquare.row = row + gKnightDeltaRow[dir];
  433.     m->toSquare.col = col + gKnightDeltaCol[dir];
  434.     m->capture = false;
  435.     if (sq->color != kEmpty) {    /* pawns need to be handled separately */
  436.         m->capture = true;
  437.         m->capturedSquare = m->toSquare;
  438.     }
  439. }
  440.  
  441. static Boolean CheckMove(Board *origBoard, ChessMove **moves, SInt16 row, SInt16 col, int dir, int dist, Piece *onSquare,UInt32 *numMovesAdded)
  442. {
  443.     ChessMove theMove;
  444.     Board b = *origBoard;
  445.     if (b.sq[row][col].rank == kKnight) {
  446.         CreateKnightMove(&theMove,row,col,dir,onSquare);
  447.     } else {
  448.         CreateMove(&theMove,row,col,dir,dist,onSquare);
  449.     }
  450.     MovePiece(&b, &theMove, b.sq[row][col].color);
  451.     if (SquareIsAttacked(&b, b.kingSq.row,b.kingSq.col)) {/* moves king into check or leaves king in check */
  452.         return false;
  453.     }
  454.     **moves = theMove;
  455.     (*moves)++;
  456.     ++*numMovesAdded;
  457.     return true;
  458. }
  459.  
  460. static Boolean CheckEPMove(Board *origBoard, ChessMove **moves, SInt16 row, SInt16 col, 
  461.         SInt16 captureRow, SInt16 captureCol,int dir, Piece *onSquare,UInt32 *numMovesAdded)
  462. {
  463.     ChessMove theMove;
  464.     Board b = *origBoard;
  465.     CreateMove(&theMove,row,col,dir,1,onSquare);
  466.     theMove.capturedSquare.row = captureRow;
  467.     theMove.capturedSquare.col = captureCol;
  468.     theMove.capture = true;
  469.     MovePiece(&b, &theMove,b.sq[row][col].color);
  470.     if (SquareIsAttacked(&b, b.kingSq.row,b.kingSq.col)) {/* moves king into check or leaves king in check */
  471.         return false;
  472.     }
  473.     **moves = theMove;
  474.     (*moves)++;
  475.     ++*numMovesAdded;
  476.     return true;
  477. }
  478.  
  479. static UInt32 CreateLegalPawnMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *origMoves)
  480. {
  481.     PieceColor ourColor = origBoard->sq[row][col].color;
  482.     PieceColor opponentColor = OtherColor(ourColor);
  483.     UInt32 numMovesAdded = 0;
  484.     Piece onSquare;
  485.     int dir,dist,homeRow,advanceRowDir,enPassantRow;
  486.     ChessMove *moves = origMoves;
  487.         
  488.     if (ourColor==kWhite) {
  489.         dir = 2;
  490.         enPassantRow = 4;
  491.         advanceRowDir = 1;
  492.     } else {
  493.         dir = 8-2;
  494.         enPassantRow = 7-4;
  495.         advanceRowDir = -1;
  496.     }
  497.     dir = ourColor==kWhite ? 2 : 8-2;    /* check moves ahead */
  498.     homeRow = (ourColor==kWhite) ? 1 : 7-1;    /* home row is 1 for white and 6 for black */
  499.     
  500.     /* check move one ahead */
  501.     dist = 1;
  502.     if (    (LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) &&
  503.             (onSquare.color == kEmpty) ) {
  504.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  505.     }
  506.     
  507.     /* check move two ahead */
  508.     dist = 2;
  509.     if (     (origBoard->pieceNeverMoved[row][col]) && 
  510.             (row == homeRow) &&
  511.             (LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) /* set onSquare */ &&
  512.             (onSquare.color == kEmpty) ){
  513.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  514.     }
  515.     
  516.     /* check capture right (including en passant) */
  517.     dir = ourColor==kWhite ? 3 : 8-3;
  518.     dist=1;
  519.     if (    LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) {
  520.         if  (onSquare.color == opponentColor) {
  521.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  522.         } else {
  523.             SInt16 epCol = col+gDeltaCol[dir];
  524.             if ( (onSquare.color == kEmpty) &&
  525.                         (row==enPassantRow) &&
  526.                         (origBoard->sq[row][epCol].rank == kPawn) &&
  527.                         (origBoard->sq[row][epCol].color == opponentColor) &&
  528.                         (origBoard->lastMove.toSquare.row == enPassantRow) &&
  529.                         (origBoard->lastMove.fromSquare.row == enPassantRow+2*advanceRowDir) &&
  530.                         (origBoard->lastMove.fromSquare.col == col + gDeltaCol[dir]) &&
  531.                         (origBoard->lastMove.toSquare.col == col + gDeltaCol[dir]) ) {
  532.                 CheckEPMove(origBoard,&moves,row,col,row,epCol,dir,&onSquare, &numMovesAdded);
  533.                     
  534. //            printf("** checking en passant (r,c)=(%d %d) ep=(%d %d)\n",
  535. //                row,col,origBoard->lastMove.fromSquare.row,origBoard->lastMove.fromSquare.col);
  536.             }
  537.         }
  538.     }
  539.     
  540.     /* check capture left (including en passant) */
  541.     dir = ourColor==kWhite ? 1 : 8-1;
  542.     dist=1;
  543.     if (    LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) {
  544.         if  (onSquare.color == opponentColor) {
  545.             CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  546.         } else {
  547.             SInt16 epCol = col+gDeltaCol[dir];
  548.             if ( (onSquare.color == kEmpty) &&
  549.                         (row==enPassantRow) &&
  550.                         (origBoard->sq[row][epCol].rank == kPawn) &&
  551.                         (origBoard->sq[row][epCol].color == opponentColor) &&
  552.                         (origBoard->lastMove.toSquare.row == enPassantRow) &&
  553.                         (origBoard->lastMove.fromSquare.row == enPassantRow-2*advanceRowDir) &&
  554.                         (origBoard->lastMove.fromSquare.col == col + gDeltaCol[dir]) &&
  555.                         (origBoard->lastMove.toSquare.col == col + gDeltaCol[dir]) ) {
  556.                 CheckEPMove(origBoard,&moves,row,col,row,epCol,dir,&onSquare, &numMovesAdded);
  557. //            printf("** checking en passant (r,c)=(%d %d) ep=(%d %d)\n",
  558. //                row,col,origBoard->lastMove.fromSquare.row,origBoard->lastMove.fromSquare.col);
  559.             }
  560.         }
  561.     }
  562.  
  563.     return moves-origMoves;
  564. }
  565.  
  566. static UInt32 CreateLegalKnightMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  567. {
  568.     PieceColor ourColor = origBoard->sq[row][col].color;
  569.     PieceColor opponentColor = OtherColor(ourColor);
  570.     UInt32 numMovesAdded = 0;
  571.     Piece onSquare;
  572.     int dir,dist=0;
  573.     
  574.     for (dir=0; dir<8; dir++) {
  575.             if (!LegalKnightRelSquare(origBoard, row, col, dir, &onSquare)) continue;
  576.             if (onSquare.color == ourColor) continue;
  577.             if ((onSquare.color == opponentColor) || (onSquare.color == kEmpty) ){
  578.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  579.                 continue;
  580.             }
  581.     }
  582.     
  583.     return numMovesAdded;
  584. }
  585.  
  586. static UInt32 CreateLegalBishopMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  587. {
  588.     PieceColor ourColor = origBoard->sq[row][col].color;
  589.     PieceColor opponentColor = OtherColor(ourColor);
  590.     UInt32 numMovesAdded = 0;
  591.     Piece onSquare;
  592.     int dir,dist;
  593.     
  594.     for (dir=1; dir<8; dir+=2) {
  595.         for (dist=1; dist<8; dist++) {    /* check distance */
  596.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  597.             if (onSquare.color == ourColor) break;
  598.             if (onSquare.color == opponentColor) {
  599.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  600.                 break;
  601.             } else if (onSquare.color == kEmpty) {
  602.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  603.                 continue;
  604.             }
  605.         }
  606.     }
  607.     
  608.     return numMovesAdded;
  609. }
  610.  
  611. static UInt32 CreateLegalRookMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  612. {
  613.     PieceColor ourColor = origBoard->sq[row][col].color;
  614.     PieceColor opponentColor = OtherColor(ourColor);
  615.     UInt32 numMovesAdded = 0;
  616.     Piece onSquare;
  617.     int dir,dist;
  618.     
  619.     for (dir=0; dir<8; dir+=2) {
  620.         for (dist=1; dist<8; dist++) {    /* check distance */
  621.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  622.             if (onSquare.color == ourColor) break;
  623.             if (onSquare.color == opponentColor) {
  624.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  625.                 break;
  626.             } else if (onSquare.color == kEmpty) {
  627.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  628.                 continue;
  629.             }
  630.         }
  631.     }
  632.     
  633.     return numMovesAdded;
  634. }
  635.  
  636. static UInt32 CreateLegalQueenMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  637. {
  638.     PieceColor ourColor = origBoard->sq[row][col].color;
  639.     PieceColor opponentColor = OtherColor(ourColor);
  640.     UInt32 numMovesAdded = 0;
  641.     Piece onSquare;
  642.     int dir,dist;
  643.     
  644.     for (dir=0; dir<8; dir++) {
  645.         for (dist=1; dist<8; dist++) {    /* check distance */
  646.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) break;
  647.             if (onSquare.color == ourColor) break;
  648.             if (onSquare.color == opponentColor) {
  649.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  650.                 break;
  651.             } else if (onSquare.color == kEmpty) {
  652.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  653.                 continue;
  654.             }
  655.         }
  656.     }
  657.     
  658.     return numMovesAdded;
  659. }
  660.  
  661. static UInt32 CreateLegalKingMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  662. {
  663.     PieceColor ourColor = origBoard->sq[row][col].color;
  664.     PieceColor opponentColor = OtherColor(ourColor);
  665.     UInt32 numMovesAdded = 0;
  666.     Piece onSquare;
  667.     int dir,dist,homeRow;
  668.  
  669.     if (ourColor==kWhite) {
  670.         homeRow = 0;
  671.     } else {
  672.         homeRow = 7;
  673.     }
  674.     
  675.     for (dir=0; dir<8; dir++) {
  676.         dist = 1;
  677.             if (!LegalRelSquare(origBoard, row, col, dir, dist, &onSquare)) continue;
  678.             if (onSquare.color == ourColor) continue;
  679.             if ( (onSquare.color == opponentColor) || (onSquare.color == kEmpty) ) {
  680.                 CheckMove(origBoard,&moves,row,col,dir,dist,&onSquare, &numMovesAdded);
  681.                 continue;
  682.             }
  683.     }
  684.     if ( (row==homeRow) && (col==kKingCol) && 
  685.                 origBoard->pieceNeverMoved[row][col] &&
  686.                 !SquareIsAttacked(origBoard, row, col)) {
  687.         ChessMove theMove;
  688.         if ( origBoard->pieceNeverMoved[row][0] &&
  689.             !SquareIsAttacked(origBoard, row, 0) && !SquareIsAttacked(origBoard, row, 1) && 
  690.             !SquareIsAttacked(origBoard, row, 2) && !SquareIsAttacked(origBoard, row, 3) && 
  691.             origBoard->sq[row][1].color==kEmpty && origBoard->sq[row][2].color==kEmpty &&
  692.             origBoard->sq[row][3].color==kEmpty ) {
  693.                 theMove.fromSquare.row = row;    theMove.fromSquare.col = col;
  694.                 theMove.toSquare.row = row;    theMove.toSquare.col = 1;
  695.                 theMove.capture = false;
  696.                 *moves = theMove;
  697.                 (moves)++;
  698.                 ++numMovesAdded;
  699.         }
  700.         if ( origBoard->pieceNeverMoved[row][7] &&
  701.             !SquareIsAttacked(origBoard, row, 7) && !SquareIsAttacked(origBoard, row, 6) && 
  702.             !SquareIsAttacked(origBoard, row, 5) && 
  703.             origBoard->sq[row][6].color==kEmpty && origBoard->sq[row][5].color==kEmpty ) {
  704.                 theMove.fromSquare.row = row;    theMove.fromSquare.col = col;
  705.                 theMove.toSquare.row = row;    theMove.toSquare.col = 6;
  706.                 theMove.capture = false;
  707.                 *moves = theMove;
  708.                 (moves)++;
  709.                 ++numMovesAdded;
  710.         }
  711.     }
  712.     
  713.     return numMovesAdded;
  714. }
  715.  
  716. static UInt32 CreateLegalMoves(Board *origBoard, SInt16 row, SInt16 col, ChessMove *moves)
  717. {
  718.     PieceRank rank = origBoard->sq[row][col].rank;
  719.     UInt32 numMovesAdded = 0;
  720.     switch (rank) {
  721.     case kPawn:
  722.         numMovesAdded = CreateLegalPawnMoves(origBoard,row,col,moves);
  723.         break;
  724.     case kKnight:
  725.         numMovesAdded = CreateLegalKnightMoves(origBoard,row,col,moves);
  726.         break;
  727.     case kBishop:
  728.         numMovesAdded = CreateLegalBishopMoves(origBoard,row,col,moves);
  729.         break;
  730.     case kRook:
  731.         numMovesAdded = CreateLegalRookMoves(origBoard,row,col,moves);
  732.         break;
  733.     case kQueen:
  734.         numMovesAdded = CreateLegalQueenMoves(origBoard,row,col,moves);
  735.         break;
  736.     case kKing:
  737.         numMovesAdded = CreateLegalKingMoves(origBoard,row,col,moves);
  738.         break;
  739.     default:
  740.         printf("** piece rank err %d\n",rank);
  741.         numMovesAdded = 0;
  742.         break;
  743.     }
  744.     return numMovesAdded;
  745. }
  746.  
  747. static UInt32 FindRemainingPieces(Board *b, ChessPiece *piece)
  748. {
  749.     int row,col;
  750.     UInt32 numPiecesRemaining = 0;
  751.     for (row=0; row<8; row++)
  752.         for (col=0; col<8; col++)
  753.             if (b->sq[row][col].color != kEmpty) {
  754.                 piece->whichColor = b->sq[row][col].color;
  755.                 piece->whichRank = b->sq[row][col].rank;
  756.                 piece->pieceLocation.row = row;
  757.                 piece->pieceLocation.col = col;
  758.                 piece++;
  759.                 numPiecesRemaining++;
  760.             }
  761.     return numPiecesRemaining;
  762. }
  763.  
  764. pascal void FindCorrectLegalChessMoves(
  765.     UInt32 numPriorMoves,
  766.     ChessMove priorMoves[],
  767.     UInt32 *numPiecesRemaining,
  768.     ChessPiece piecesRemaining[],
  769.     UInt32 *numLegalMoves,
  770.     ChessMove legalMoves[]
  771. ) {
  772.     int i;
  773.     SInt16 row,col;
  774.     Board bd;
  775.     UInt32 myNumLegalMoves = 0;
  776.     UInt32 myNumPiecesRemaining = 0;
  777.     PieceColor colorToMove = kWhite;
  778.     InitBoard(&bd);
  779.     PrintBoard(&bd);
  780.     for (i=0; i<numPriorMoves; i++) {
  781.         MovePiece(&bd,&priorMoves[i],colorToMove);
  782.         PrintBoard(&bd);
  783.         colorToMove = OtherColor(colorToMove);
  784.     }
  785.     myNumPiecesRemaining = FindRemainingPieces(&bd, piecesRemaining);
  786.     for (row=0; row<8; row++)
  787.         for (col=0; col<8; col++)
  788.             if (bd.sq[row][col].color == colorToMove)
  789.                 myNumLegalMoves += CreateLegalMoves(&bd,row,col,legalMoves+myNumLegalMoves);
  790.     *numPiecesRemaining= myNumPiecesRemaining;
  791.     *numLegalMoves = myNumLegalMoves;
  792. }
  793.  
  794. pascal OSErr CheckChess( const FSSpec* infile, const FSSpec* outfile, Boolean *correct )
  795. {
  796.     OSErr err;
  797.     Handle indata;
  798.     int j;
  799.     UInt32 numPriorMoves,numPiecesRemaining,numLegalMoves,numCorrectPiecesRemaining,numCorrectLegalMoves;
  800.     ChessPiece *piecesRemaining,*correctPiecesRemaining;
  801.     ChessMove *priorMoves,*correctPriorMoves,*legalMoves,*correctLegalMoves;
  802.  
  803.     printf( "Starting Chess\n" );
  804.     *correct = TRUE;
  805.     
  806.     err = ProblemFileRead( infile, &indata );
  807.     if ( err == noErr ) {
  808.         err = ReadUInt32FromHandle( indata, &numPriorMoves );
  809.  
  810.         piecesRemaining = (ChessPiece *)NewPtr(kMaxPiecesRemaining*sizeof(ChessPiece));
  811.         if (0==piecesRemaining) DebugStr("\p problem allocating piecesRemaining");
  812.         legalMoves = (ChessMove *)NewPtr(kMaxMoves*sizeof(ChessMove));
  813.         if (0==legalMoves) DebugStr("\p problem allocating legalMoves");
  814.         priorMoves = (ChessMove *)NewPtrClear((1+numPriorMoves)*sizeof(ChessMove));
  815.         if (0==priorMoves) DebugStr("\p problem allocating priorMoves");
  816.         
  817.         ReadMoves(indata, numPriorMoves, priorMoves);
  818.  
  819.         FindLegalChessMoves(numPriorMoves,priorMoves,&numPiecesRemaining,piecesRemaining,
  820.             &numLegalMoves,legalMoves);
  821.  
  822.         /* sort pieces remaining and legal moves */
  823.         FastQSort((void *)piecesRemaining,(long)numPiecesRemaining,(long)sizeof(ChessPiece),SortPiecesCmp);
  824.         FastQSort((void *)legalMoves,(long)numLegalMoves,(long)sizeof(ChessMove),SortMovesCmp);
  825.  
  826.         PrintPieces(numPiecesRemaining, piecesRemaining,"Number of pieces remaining reported");
  827.         PrintMoves(numLegalMoves, legalMoves,"Number of moves reported");
  828.         
  829.         correctPiecesRemaining = (ChessPiece *)NewPtr(kMaxPiecesRemaining*sizeof(ChessPiece));
  830.         if (0==correctPiecesRemaining) DebugStr("\p problem allocating correctPiecesRemaining");
  831.         correctLegalMoves = (ChessMove *)NewPtr(kMaxMoves*sizeof(ChessMove));
  832.         if (0==correctLegalMoves) DebugStr("\p problem allocating correctLegalMoves");
  833.         correctPriorMoves = (ChessMove *)NewPtrClear((1+numPriorMoves)*sizeof(ChessMove));
  834.         if (0==correctPriorMoves) DebugStr("\p problem allocating correctPriorMoves");
  835.         BlockMove(priorMoves,correctPriorMoves,numPriorMoves*sizeof(ChessMove));
  836.  
  837.         FindCorrectLegalChessMoves(numPriorMoves,correctPriorMoves,&numCorrectPiecesRemaining,correctPiecesRemaining,
  838.             &numCorrectLegalMoves,correctLegalMoves);
  839.  
  840. #if PRINT_CORRECT_RESULTS
  841.         PrintPieces(numCorrectPiecesRemaining, correctPiecesRemaining,"Correct number of pieces remaining");
  842.         PrintMoves(numCorrectLegalMoves, correctLegalMoves,"Correct number of moves");
  843. #endif
  844.  
  845.         /* sort pieces remaining and legal moves */
  846.         FastQSort((void *)correctPiecesRemaining,(long)numCorrectPiecesRemaining,(long)sizeof(ChessPiece),SortPiecesCmp);
  847.         FastQSort((void *)correctLegalMoves,(long)numCorrectLegalMoves,(long)sizeof(ChessMove),SortMovesCmp);
  848.  
  849.         if (numPiecesRemaining != numCorrectPiecesRemaining) {
  850.             *correct = false;
  851.         } else {
  852.             for (j=0; j<numCorrectPiecesRemaining; j++) {
  853.                 if ( (piecesRemaining[j].whichColor != correctPiecesRemaining[j].whichColor) ||
  854.                       (piecesRemaining[j].whichRank != correctPiecesRemaining[j].whichRank) ||
  855.                       (piecesRemaining[j].pieceLocation.col != correctPiecesRemaining[j].pieceLocation.col) ||
  856.                       (piecesRemaining[j].pieceLocation.row != correctPiecesRemaining[j].pieceLocation.row) )
  857.                           *correct = false;
  858.             }
  859.             if (numLegalMoves != numCorrectLegalMoves) {
  860.                 *correct = false;
  861.             } else {
  862.                 for (j=0; j<numCorrectLegalMoves; j++) {
  863.                     if ( (legalMoves[j].fromSquare.col != correctLegalMoves[j].fromSquare.col) ||
  864.                           (legalMoves[j].fromSquare.row != correctLegalMoves[j].fromSquare.row) ||
  865.                           (legalMoves[j].toSquare.col != correctLegalMoves[j].toSquare.col) ||
  866.                           (legalMoves[j].toSquare.row != correctLegalMoves[j].toSquare.row) ||
  867.                           (legalMoves[j].capture != correctLegalMoves[j].capture) ||
  868.                           (correctLegalMoves[j].capture &&
  869.                               (    (legalMoves[j].capturedSquare.col != correctLegalMoves[j].capturedSquare.col) || 
  870.                                   (legalMoves[j].capturedSquare.row != correctLegalMoves[j].capturedSquare.row) )) )
  871.                                       *correct = false;
  872.                 }
  873.             }
  874.         }
  875.         
  876.         if (correctPriorMoves) DisposePtr((Ptr)correctPriorMoves);
  877.         if (correctLegalMoves) DisposePtr((Ptr)correctLegalMoves);
  878.         if (correctPiecesRemaining) DisposePtr((Ptr)correctPiecesRemaining);
  879.         if (priorMoves) DisposePtr((Ptr)priorMoves);
  880.         if (legalMoves) DisposePtr((Ptr)legalMoves);
  881.         if (piecesRemaining) DisposePtr((Ptr)piecesRemaining);
  882.     }
  883. //    printf("Done.\n");
  884.     if (indata) DisposeHandle(indata);
  885.     
  886.     return noErr;
  887. }
  888.  
  889.